{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simulating a Random Walk\n",
    "===============\n",
    "\n",
    "Introduction\n",
    "-----------\n",
    "Very often in physics, we find ourselves needing to approximate some quantity of interest. If analytic methods fail, we may turn to numerical simulation. A large class of such algorithms goes by the name of [Monte Carlo](https://en.wikipedia.org/wiki/Monte_Carlo_method). Some of the original algorithms in this field date to the work of von Neumann and Ulam during the Manhattan Project.\n",
    "\n",
    "Briefly, Monte Carlo allows us to approximate a quantity of interest by _random sampling_. In this lesson, we simulate the behavior of a simple random walk.\n",
    "\n",
    "\n",
    "Random Walks\n",
    "---------\n",
    "\n",
    "One of the simplest random walks we could consider goes like this:\n",
    "\n",
    "* At time $t=0$, start the walker in position $X_{0} = 0$.\n",
    "\n",
    "* For each timestep in $[1,2,3,\\cdots, T]$, update the position as\n",
    "$$X_{t} = X_{t-1} + \\Delta_{j}$$\n",
    "where $\\Delta_{j}$ is a random variable satisfying\n",
    "\n",
    "$$\\Delta_{j} =\\begin{cases}+1~~~~~\\text{with probability $p$} \\cr -1~~~~\\text{with probability $1-p$}\\end{cases}$$\n",
    "\n",
    "That is, the direction the walker moves is determined by the outcome of a coin whose probability of coming up heads is $p$.\n",
    "\n",
    "Notice that $X_{t}$ may be simply written as\n",
    "\n",
    "$$X_{t} = \\sum_{j=1}^{t}\\Delta_{j}$$\n",
    "\n",
    "In addition, $X_{T}$ is the total _displacement_ of the walker after $T$ timesteps.\n",
    "\n",
    "We will be interested in simulating several properties of this walk:\n",
    "\n",
    "**Trajectories**\n",
    "\n",
    "A _trajectory_ of the walk is simply a collection of values for $X_{t}$. For fixed values of $p$ and $T$, what kind of trajectories do we see?\n",
    "\n",
    "**Mean Displacement**\n",
    "\n",
    "What is the behavior of $\\langle X_{T} \\rangle$ -- where we average of many trajectories -- as a function of $p$ and $T$?\n",
    "\n",
    "\n",
    "**Variance of the Displacement**\n",
    "\n",
    "What is the behavior of $(\\Delta X_{T})^{2} = \\langle X_{T}^{2}\\rangle - \\langle X_{T}\\rangle^{2}$ as a function of $p$ and $T$?\n",
    "\n",
    "\n",
    "**How do I do these simulations quickly?**\n",
    "\n",
    "We'll write progressively more efficient code to do the simulations, as measured by the amount of time it takes us to compute an answer. Along the way, we will see how [_vectorization_ of our code](https://en.wikipedia.org/wiki/Array_programming) gives us significant speedups. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Preliminaries\n",
    "===========\n",
    "\n",
    "For this lesson, we rely on ``numpy``, ``matplotlib``, and ``seaborn``. We will also be using some of the [iPython magic commands](http://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=magic)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'''\n",
    "Import numpy, matplotlib, and seaborn.\n",
    "Don't forget to use the magic %matplotlib inline\n",
    "to render the figures inside the notebook!\n",
    "'''\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Building a Simulator\n",
    "=============\n",
    "My first intuition about how to do this simulation revolved around figuring out how to compute single trajectories. One of the more obvious ways of doing so would go as follows:\n",
    "\n",
    "* Fix a value for the coin's bias.\n",
    "* Initialize the displacement of the walker to be zero.\n",
    "* For each timestep, flip a coin. If it comes up heads, increment the displacement by one; else, decrement it by one. Store the new value of the displacement in a list.\n",
    "* To obtain multiple trajectories, repeat the two steps above many times.\n",
    "* To obtain multiple trajectories for different values of the bias, repeat the four steps above multiple times.\n",
    "\n",
    "Below we code up this approach by building several different functions:\n",
    "\n",
    "* `convert_value`: Converts the outcome of a binomial experiment to $\\pm 1$.\n",
    "* `single_update`: Draws a random value for the step $\\Delta$\n",
    "* `single_trajectory`: Computes a single trajectory for a walk\n",
    "* `multiple_trajectories`: Computes many trajectories\n",
    "\n",
    "Finally, we use the iPython magic ``%%time`` to qualitatively examine what happens to the runtime of the code as we iterate over $p,T$, and the number of trajectories we simulate.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approach I: (Many) Nested ``for`` loops\n",
    "====\n",
    "\n",
    "The most straightforward approach is to write a whole bunch of ``for`` loops.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def convert_value(value):\n",
    "    r'''\n",
    "    Maps a binary value to 1 or -1, under the mapping\n",
    "        x -> x -1 + max(0, x)\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    value: A value to be converted. Can be float or integer. \n",
    "           To obtain expected behavior, value must be either 0 or 1\n",
    "    \n",
    "    Returns\n",
    "    ---------\n",
    "    converted_value: The value converted to 1 or -1, \n",
    "                    where value = 0 is converted to -1, and \n",
    "                    value = 1 is converted to 1\n",
    "    '''\n",
    "    \n",
    "    \n",
    "    \n",
    "    return converted_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def single_update(p):\n",
    "    r'''Computes a single step $Delta$ for the random walk\n",
    "    \n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    step: A random step whose distribution is\n",
    "          +1 with probability p, and\n",
    "          -1 with probability (1-p) \n",
    "    '''\n",
    "    \n",
    "    #Draw a binomially-distributed random variable\n",
    "\n",
    "    \n",
    "    #Convert that variable to a step\n",
    "    \n",
    "    return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def single_trajectory(p, T, Seed):\n",
    "    r'''\n",
    "    Computes a single trajectory of a random walk\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    Seed: A seed for numpy's random number generator. Must be an integer\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    displacements: A numpy array with one row and T columns whose j^th entry\n",
    "                      is the displacement of the random walker at timestep j\n",
    "    '''\n",
    "    \n",
    "    #Initialize a list and\n",
    "    #a displacement counter\n",
    "\n",
    "    \n",
    "    #Set numpy's random seed\n",
    "    \n",
    "    #execute the walk using a for loop\n",
    "\n",
    "        \n",
    "    return displacements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiple_trajectories(p, T, numTrajectories):\n",
    "    r'''\n",
    "    Simulates multiple trajectories of a random walk\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    numTrajectories: The total number of trajectories to simulate. Must be an integer\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    trajectories: A numpy array of length numTrajectories whose j^th element is the j^th simulated trajectory\n",
    "                       (which is itself of length T)\n",
    "    '''\n",
    "    \n",
    "    #Initialize the list of trajectories\n",
    "    \n",
    "    #Simulate multiple trajectories\n",
    "    #using a for loop\n",
    "\n",
    "        \n",
    "    #Cast it as a numpy array\n",
    "    \n",
    "    return trajectories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a simulator for our random walk, let's check out how long it tends to take to run it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "#To suppress the output of the function\n",
    "#call, assign it to a variable!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even though the code seems \"fast\" for simulating a single trajectory, if we wanted to iterate over many different values of $p$, those times would add up. Looking back through the code, we see there are 2 ``for`` loops. Generally speaking, the more ``for`` loops you have, the slower your code will run. This has less to do with ``for`` somehow intrinsically taking a long time to execute in Python, and more to do with the fact that ``for`` loops run for as long as you let them. So if we simulate longer and longer walks, or want to create more and more trajectories, the ``for`` loops are going to cause a signficant increase in runtime.\n",
    "\n",
    "If we wanted to compute $M$ trajectories, each of length $T$, for $P$ values of $p$, then the total runtime of our code above would scale as $\\mathcal{O}(MPT)$.\n",
    "\n",
    "While it would be good to use a tool (such as a line profiler) to check where exactly the code takes a long time to execute, an inspection of it suggests at least one way to speed up the computation, and that's by improving the performance of ``single_trajectory``. It's to that problem that we now turn."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approach II - Vectorizing ``single_trajectory``\n",
    "----------------------\n",
    "\n",
    "The two lowest-level functions we use are ``convert_value`` and ``single_trajectory``. If we can speed up the runtimes of those two functions, then we can gain some speed advantage.\n",
    "\n",
    "To do so, we utilize ``numpy`` array objects, which provide a more restricted kind of data type than a Python list. Using these arrays provides us with (at least) two benefits:\n",
    "\n",
    "* We may use _vectorized_ operations. If I have two arrays, $a$ and $b$, calling $a+b$ does element-wise addition. In contrast, Python lists do not support such an operation. Further, numpy comes with many functions which can be applied to numpy arrays (for example, the sine and cosine functions), and which are evaluated in an efficient manner. (MATLAB offers similar functionality.)\n",
    "\n",
    "* We may use [array _broadcasting_](https://docs.scipy.org/doc/numpy/user/basics.broadcasting.html) to efficiently do simple scalar operations on arrays. For example, taking a numpy array $a$, and calling $a+1$, causes numpy to evaluate the addition _as if_ the number 1 is treated as an array whose shape is $a$.\n",
    "\n",
    "In this section, we vectorize ``convert_value`` and ``single_trajectory``, which will speed up the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def vectorized_convert_value(value):\n",
    "    r'''\n",
    "    Maps  a binary value to 1 or -1, under the mapping\n",
    "        x -> x - 1 + max(0, x)\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    value: A value to be converted. Can be float or integer,\n",
    "           or a numpy array containing floats or integers.\n",
    "           To obtain expected behavior, value must be either 0 or 1\n",
    "    \n",
    "    Returns\n",
    "    ---------\n",
    "    converted_value: The value converted to 1 or -1, \n",
    "                    where value = 0 is converted to -1, and \n",
    "                    value = 1 is converted to 1. If input\n",
    "                    is numpy array, then output is numpy array as well.\n",
    "    '''   \n",
    "    \n",
    "    \n",
    "    return converted_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Call ``vectorized_convert_value`` with a numpy array of zeros and ones, and see what happens!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By inputting an array, the output is also an array, whose elements are the actions of our function on the individual elements.\n",
    "\n",
    "To vectorize ``single_trajectory``, we need to know that numpy's ``random.binomial()`` function can return an _array_ of values, not just a scalar. We access that functionality using the ``size`` keyword argument. This allows us to declare, in a single function call, the results of _all_ the coin tosses used in the simulation.\n",
    "\n",
    "We also then use numpy's ``cumsum()`` function to compute the cumulative sum of the elemements of the array, thereby providing us with the trajectory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def vectorized_single_trajectory(p, T, Seed):\n",
    "    r'''\n",
    "    Computes a single trajectory of a random walk\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    Seed: A seed for numpy's random number generator. Must be an integer\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    displacements: A numpy array with one row and T columns whose j^th entry\n",
    "                      is the displacement of the random walker at timestep j\n",
    "    '''\n",
    "    \n",
    "    #Set the random seed\n",
    "\n",
    "    \n",
    "    #Generate an array of binomially-distributed\n",
    "    #random variables whose length is T\n",
    "\n",
    "    \n",
    "    #Convert those values to steps\n",
    "\n",
    "    \n",
    "    #Compute the cumulative sum of the values -\n",
    "    #that gives us the displacements\n",
    "\n",
    "    \n",
    "    return displacements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check to make sure that our vectorized version gives the same trajectories as our original ``single_trajectory`` function. To do that, we create the ``check_vec`` function below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def check_vec(p, T, Seed):\n",
    "    r'''\n",
    "    Checks whether the trajectory computed by vecotrized_single_trajectory\n",
    "    agrees with that computed by single_trajectory.\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    Seed: A seed for numpy's random number generator. Must be an integer\n",
    "    \n",
    "    Returns\n",
    "    -----\n",
    "    None. Raises an AssertionError if the two trajectories disagree in any position.\n",
    "    \n",
    "    '''\n",
    "    difference = vectorized_single_trajectory(p, T, Seed) - np.array(single_trajectory(p, T, Seed))\n",
    "    \n",
    "    assert np.isclose(difference, 0).all(), 'Vectorization failed'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using ``check_vec``, we can iterate over values of $p,T$ and ``Seed`` to check if the vectorized code gives the same results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have done the check, let's re-write ``multiple_trajectories`` to use ``vectorized_single_trajectory`` instead. This amounts to a change in a single line of the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiple_trajectories(p, T, numTrajectories):\n",
    "    r'''\n",
    "    Simulates multiple trajectories of a random walk\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    numTrajectories: The total number of trajectories to simulate. Must be an integer\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    trajectories: A numpy array of length numTrajectories whose j^th element is the j^th simulated trajectory\n",
    "                       (which is itself of length T)\n",
    "    '''\n",
    "    \n",
    "    #Initialize the list of trajectories\n",
    "    \n",
    "    #Simulate multiple trajectories\n",
    "    #using a for loop\n",
    "\n",
    "        \n",
    "    #Cast it as a numpy array\n",
    "    \n",
    "    return trajectories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's go ahead and time our new ``multiple_trajectories`` function. (You should call it with the same inputs used when we timed the original version.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wow! We achived some speedup simply by changing how we computed a single trajectory.\n",
    "\n",
    "In a production environment (or because you are curious), you could create a _regression test_ which takes as input values of $p,T$, and the number of trajectories, and which outputs the runtime of the original ``multiple_trajectories`` and its vectorized version. This would be useful in case someone (such as your advisor!) wanted to know whether the changes \"actually provided a speedup\". Writing such a test would probably involve learning how to use a profiler of sorts, and learning more about better ways of timing code execution.\n",
    "\n",
    "In the last part of this lesson, we will show how to vectorize ``multiple_trajectories`` itself, and in the process, eliminating the ``single_trajectories`` function entirely from the simulation. While this change may not always provide a speedup, it _does_ make the code a bit more robust and easier to follow (once you understand ``numpy`` arrays)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approach III - Vectorizing ``multiple_trajectories``\n",
    "===============\n",
    "\n",
    "Our previous approach utilized the fact that we could declare, in a single function call, the results of all the coin flips the walker would take. We did so by changing the _size_ of the array of random variables returned by ``np.random.binomial``. However, numpy arrays are intrinsically _multi-dimensional_, meaning we can also use a single function call to obtain the results of all the coin flips __for all of the walkers__. In this way, we will have vectorized the random walk, not just over each individual trajectory, but over all the trajectories themselves!\n",
    "\n",
    "In turn, this means we won't need to have a ``single_trajectories`` function to calculate a single trajectory - we'll compute the coin tosses and cumulative displacements for all the trajectories in a single go."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiple_trajectories(p, T, numTrajectories, startSeed=0):\n",
    "    r'''\n",
    "    Simulates multiple trajectories of a random walk\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    p: The bias of the coin determining the random walk\n",
    "    \n",
    "    T: The total number of timesteps. Must be an integer.\n",
    "    \n",
    "    numTrajectories: The total number of trajectories to simulate. Must be an integer\n",
    "    \n",
    "    startSeed: A seed for numpy's random number generator. Optional.\n",
    "    \n",
    "    Returns\n",
    "    ------\n",
    "    trajectories: A numpy array of shape (numTrajectories,T) whose j^th row is the j^th simulated trajectory\n",
    "                       (which is itself of length T)\n",
    "    '''\n",
    "    \n",
    "    #Set the random seed\n",
    "\n",
    "    \n",
    "    #Generate an array of binomially-distributed\n",
    "    #random variables whose shape is numTrajectories\n",
    "    #rows, and T columns\n",
    "\n",
    "    \n",
    "    #Vectorize these values\n",
    "\n",
    "    \n",
    "    #The displacements are again a cumulative sum\n",
    "    #but when calling np.cumsum(), we need to compute\n",
    "    #it over axis=1 (the columns)\n",
    "\n",
    "    \n",
    "    return trajectories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this single function, we've now managed to simplify our code for the random walk. Let's time it and see what we find."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While the runtime seems to have gone down some, it's not entirely clear whether that decrease is actually significant. Again, we'd want to create a regression test to check that out, or look at the _distribution_ of runtimes for each version of ``multiple_trajectories``."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Examining the Behavior of a Random Walk\n",
    "====================\n",
    "\n",
    "Now that we have a fast simulator for our random walk, let's go back  to the questions which started us down this line of inquiry in the first place. Below, we examine the behavior of the random walk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Characteristic Trajectories\n",
    "------------\n",
    "\n",
    "Because ``multiple_trajectories`` returns a numpy array whose rows are single trajectories, we can quickly generate plots of trajectories for fixed values of $p$ and $T$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Instantiate a matplotlib figure\n",
    "#and axes\n",
    "\n",
    "#Pick some values for p, T, and the number of trajectories\n",
    "\n",
    "\n",
    "\n",
    "#Create an array whose elements are\n",
    "#a single trajectory\n",
    "\n",
    "\n",
    "#Loop over the trajectories\n",
    "#and plot them\n",
    "\n",
    "\n",
    "#Set the title, xlabel, and ylabel\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Mean Value of the Displacement\n",
    "----------------\n",
    "\n",
    "To examine the behavior of $\\langle X_{T} \\rangle$, we create many trajectories, and then average over them. Again, because the output of ``multiple_trajectories`` stores each trajectory in a single _row_ of the output, we can average over the displacements at each timestep using ``np.mean``, and passing in an appropriate keyword argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Instantiate a figure and axis\n",
    "\n",
    "\n",
    "#Set the number of timesteps,\n",
    "#number of trajectories, and\n",
    "#the values for p\n",
    "\n",
    "#Loop over the p-values, compute multiple\n",
    "#trajectories, take their mean (w/ axis=0), and plot them\n",
    "\n",
    "\n",
    "#Set a legend\n",
    "\n",
    "\n",
    "#Set the title, xlabel, and ylabel\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the definition of $X_{T}$, we can compute its expected value analytically:\n",
    "\n",
    "$$\\langle X_{T} \\rangle = \\sum_{j=1}^{T}\\langle \\Delta_{j} \\rangle = \\sum_{j=1}^{T}(1*p -1*(1-p)) = (2p-1)T$$\n",
    "\n",
    "Looking at our plot above, our simulation conforms to that behavior."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extensions\n",
    "========\n",
    "\n",
    "Here are a few extensions of this lesson which might be of interest:\n",
    "\n",
    "* Make a plot of the variance of the walk versus $T$.\n",
    "    * To help you understand the behavior of this plot, you may want to make a plot of the variance at some fixed time $t$ versus $p$. You should find it is symmetric with respect to the transformation $p \\rightarrow 1-p$.\n",
    "* Un-vectorize ``compute_value()`` to allow for a random walk where the step sizes to the left and right are different. You may be able to re-vectorize it using ``numpy.vectorize()``.\n",
    "\n",
    "* Use the simulator to compute the probability $X_{T}$ has some fixed value $x$, as a function of $T$ and $p$. (This is related to the _hitting time_ of the walk.)\n",
    "\n",
    "* Consider two random walkers who start at different initial positions. What's the probability that one walker overtakes the other after $T$ timesteps, as a function of $p$ and the starting positions?\n",
    "\n",
    "* Generalize the code to walk on a $d$-dimensional lattice/space. (You'll need to be careful about the axes of numpy arrays!) What can you see about the behavior of the mean displacement? The variance?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
